class Solution {
public:
    //方法一：
    // void dfs(vector<int>& nums, int index)
    // {
    //     if (index == nums.size())
    //         return;
    //     for (int i = index; i < nums.size(); i++)
    //     {
    //         path.push_back(nums[i]);

    //         ret.push_back(path);
    //         dfs(nums, i + 1);

    //         path.pop_back();
    //     }
    // }

    // vector<vector<int>> subsets(vector<int>& nums) {
    //     ret.push_back(vector<int>());
    //     dfs(nums, 0);

    //     return ret;
    // }


    //方法二：
    void dfs(vector<int>& nums, int index)
    {
        if (index == nums.size())
        {
            ret.push_back(path);
            return;
        }
        
        //不选当前位置
        dfs(nums, index + 1);

        //选当前位置
        path.push_back(nums[index]);
        dfs(nums, index + 1);
        path.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);

        return ret;
    }
private:
    vector<vector<int>> ret;
    vector<int> path;
}; 